This invention relates generally to facsimile image data compression and, in particular, to border-following compression including a resolution changing apparatus and process.
1. Field of the Invention
Data compression is necessary in order to store the coded points in any two dimensional array representative of a black/white image since the amount of data received is so large as to exceed the boundaries of any reasonable cost memory store. In the prior art, the image is scanned and the data received is compressed in some fashion such as a predictive run length encoding in order to substantially decrease the amount of data necessary for a successful reproduction. More recently data compression has been accomplished utilizing boundary following of the exterior and interior borders of objects. The image is considered to be a two-dimensional array of points each of which exhibit a Boolean value representative of a black or white picture element. A cluster of black elements is defined as an object if it possesses a single outer boundary closing upon itself.
A contour coded image is a list of objects. Each entry in the list is an object, its location and shape precisely described in the chain coded format. Any hole possessed by a given object is described by subordinate chains by that particular entry. The chain header, in addition to specifying object location, may contain information as to structure for order list-type applications.
This coded data by virtue of its organization by entity can be processed in ways that cause meaningful image manipulation operations to be realized. This category of operations are called information preserving in that the contours are not irreversibly modified. Examples of this include rotation of images, editing or merging images, and form removal. Some of these operations may involve the irreversible deletion of entire contours, but they are still called manipulation functions.
A second class of operations that may be conveniently performed in the contour domain is called image processing and is characterized by an irreversible modification of the contours themselves. Examples of these operations include noise removal, smoothing, skeletonization (that is, thinning) and resolution changing. A method and apparatus for the contour resolution change of the compressed data information utilizing boundary following is the subject of this invention.
A resolution changing operation is frequently required at an input/output device. If an image is scanned, it may be desirable to store the image at a resolution different from that of the sensor device. It may also be desirable to print or display an image on a device whose resolution is different from the stored image resolution. The mechanism must be able to change resolutions by any reduction or expansion ratio. That ratio must be dynamically selectable.
2. Description of the Prior Art
A compression method and apparatus for black/white images is known as contour coding and is the subject of a U.S. Pat. No. 3,987,412 assigned to the assignee of the present invention. Briefly, the encoding process of that patent involves locating all of the edges in an image and chain coding these picture elements as objects and boarders of a whole in a systematic manner. A chain is a series of moves from image point to neighboring image point. In the patent, the chain moves around the border. Images are encoded and reconstructed by means of a border follower. The encoded images are stored in a random access addressable image memory.
The notion of boundary encoding, as suggested above, of the outer contours of black objects on a white background is not new. Methods for acheiving these results may be found in Rosenfield, "Picture Processing by Computer," Academic Press, New York, Library of Congress 78-84255, at pages 134-138. Also one may find methods in the literature which locates an organized list of object boundary contours. However, most of the methods appear to operate on grey scale information. The few black/white algorithms appearing in the literature are at least partially raster based thus requiring many passes over the entire array. Typically, the piror art methods require several bits of storage for each picture element being processed.
In the prior art, the resolution changing operations have been implemented for conversion ratios that are integers only. A two to one consolidation is done by taking each two by two block of picture elements and generating a single resultant picture element based on a "majority" among the four input picture elements. This is accomplished in the prior art, for example, on a scanning device where the scan head resolution is double the resolution that is desired for storage.
It is, therefore, a primary object of the present invention to provide a universal resolution changing mechanism for use with a contour coding apparatus that has the ability to change resolutions by any dynamically selectable reduction ratio.